package org.hot100_5.leetcode146;

import java.security.Key;
import java.util.HashMap;

public class Solution {
    class LRUCache {

        class Node {
            int key;
            int value;
            Node next;
            Node pre;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        private final int size;

        Node dummy;

        HashMap<Integer, Node> hashMap = new HashMap<>();

        public LRUCache(int capacity) {
            this.size = capacity;
            dummy = new Node(-1, -1);
            dummy.next = dummy;
            dummy.pre = dummy;
        }

        public int get(int key) {
            Node node = getNode(key);
            if (node==null){
                return -1;
            }
            return node.value;
        }

        public void put(int key, int value) {
            if (hashMap.containsKey(key)){
                Node node = getNode(key);
                node.value = value;
            }else {
                Node newNode = new Node(key,value);
                hashMap.put(key,newNode);
                if (hashMap.size()>size){
                    Node removNode = dummy.pre;
                    hashMap.remove(removNode.key);
                    removeNode(removNode);
                }
                putNodeHeader(newNode);
            }
        }

        public Node getNode(int key) {
            if (hashMap.containsKey(key)) {
                Node node = hashMap.get(key);
                //先删节点，再将节点移动到头部
                removeNode(node);
                putNodeHeader(node);
                return node;
            }

            return null;
        }


        private void putNodeHeader(Node node) {
            dummy.next.pre = node;
            node.next = dummy.next;
            dummy.next = node;
            node.pre = dummy;
        }

        private void removeNode(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }


    }
}
